package Queue_and_Stack;

/*
设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。
但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

示例：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/queue-stack/kzlb5/
 */

public class _11设计循环队列 {

    //数组         存在O(k)     O(k)
    class MyCircularQueue {
        int head = -1, tail = -1;
        Integer[] queue;
        int size = 0;
        public MyCircularQueue(int k) {
            queue = new Integer[k];
            size = k;
        }

        public boolean enQueue(int value) {
            if(!isFull()){
                tail++;
                if(tail == size){
                    tail = 0;
                }
                queue[tail] = value;
                if(head == -1){
                    head = tail;
                }
                return true;
            }
            return false;
        }

        public boolean deQueue() {
            if (!isEmpty()){
                queue[head] = null;
                head++;
                if(head == size){
                    head = 0;
                }
                return true;
            }
            return false;

        }

        public int Front() {
            if(head == -1){
                return -1;
            }
            if (queue[head] != null){
                return queue[head];
            }
            return -1;
        }

        public int Rear() {
            if(tail == -1){
                return -1;
            }
            if (queue[tail] != null){
                return queue[tail];
            }
            return -1;
        }

        public boolean isEmpty() {
            for (int i = 0; i < size; i++) {
                if (queue[i] != null){
                    return false;
                }
            }
            return true;
        }

        public boolean isFull() {
            for (int i = 0; i < size; i++) {
                if (queue[i] == null)
                    return false;
            }
            return true;
        }
    }

    //官解：数组   O(1)  O(k)
    //在循环队列中，当队列为空，可知front=rear；而当所有队列空间全占满时，也有 front=rear。
    //为了区别这两种情况，假设队列使用的数组有 capacity 个存储空间，则此时规定循环队列最多只能有capacity−1 个队列元素，当循环队列中只剩下一个空存储单元时，则表示队列已满。
    //根据以上可知，队列判空的条件是 front=rear，而队列判满的条件是 front=(rear+1)modcapacity。
    //由此，isFull 和 isEmpty 便变得简单
    class MyCircularQueue2 {
        private int front;
        private int rear;
        private int capacity;
        private int[] elements;

        public MyCircularQueue2(int k) {
            capacity = k + 1;
            elements = new int[capacity];
            rear = front = 0;
        }

        public boolean enQueue(int value) {
            if (isFull()) {
                return false;
            }
            elements[rear] = value;
            rear = (rear + 1) % capacity;
            return true;
        }

        public boolean deQueue() {
            if (isEmpty()) {
                return false;
            }
            front = (front + 1) % capacity;
            return true;
        }

        public int Front() {
            if (isEmpty()) {
                return -1;
            }
            return elements[front];
        }

        public int Rear() {
            if (isEmpty()) {
                return -1;
            }
            return elements[(rear - 1 + capacity) % capacity];
        }

        public boolean isEmpty() {
            return rear == front;
        }

        public boolean isFull() {
            return ((rear + 1) % capacity) == front;
        }
    }


}


